P14582 [LNCPC 2025] 被抠的键盘 题解

本文迁移自洛谷原文。

首先发现 $0$ 是一定没有被抠掉的。如果没有其他别的数字，那么只有 $0$ 显然是无法得到 $m$ 的正整数倍数，输出 $-1$。

考虑将 $m$ 除去其所有 $2,5$ 因子得到 $m’$，那么 $m’$ 与 $10$ 互质。由欧拉定理得，$10^{\phi(9m’)} \equiv 1 \pmod {9m’}$，即 $\phi (9m’)$ 个 $1$ 是 $m’$ 的倍数。再考虑把 $m’$ 补为 $m$ 的过程，即乘上很多 $2$ 和 $5$，只需要在我们的构造后面添上足够多的 $0$ 即可。

现在我们得到了仅用 $0,1$ 就能构造的方案，显然把 $1$ 换为任意非 $0$ 数字均成立。由于 $m \le 10^7$，所以不能直接计算 $\phi (9m’)$。我们预处理到 $10^7$，然后由 $\phi (9m’) \mid 18\phi (m’)$ 得，可以输出 $18 \phi(m’)$ 个相同的任意没被抠掉的数字，最后输出 $10^9$ 个 $0$ 即可，仅需两步。